﻿
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WindowsGame2.Map
{
    public class TILE_POSITION
    {
        
        public int m_x;
        public int m_y;

        public TILE_POSITION(int x, int y)
        {
            m_x = x;
            m_y = y;
        }
        public int getLinearIndex(int width)
        {
            return width * m_y + m_x;
        }        
    }

    
    public class ADJACENCY
    {
	    public TILE_POSITION				m_position;
	    public List<ADJACENCY>		        m_adjacencyList;

	    public enum STATE
	    {
		    INIT,
		    OPEN,
		    CLOSE,
	    };

	    public STATE						m_state;
        public ADJACENCY m_pCallee;
	
	    public class AStarDesc
	    {
		    public int m_f;
            public int m_g;
            public int m_h;
            public int m_weight;
		    public AStarDesc()
            {
                reset();
            }

            public void reset()
            {
                m_f = 0;
                m_g = 0;
                m_h = 0;
                m_weight = 0;
            }

		    public static void calculate(TILE_POSITION goal, ADJACENCY fromAdjacency, ADJACENCY toAdjacency, AStarDesc astarDesc)
		    {
			    astarDesc.m_h = (Math.Abs(goal.m_x - toAdjacency.m_position.m_x) + Math.Abs(goal.m_y - toAdjacency.m_position.m_y))*10;

			    // 대각선이라면
			    if (toAdjacency.m_position.m_x != fromAdjacency.m_position.m_x && toAdjacency.m_position.m_y != fromAdjacency.m_position.m_y)
			    {
                    astarDesc.m_g = fromAdjacency.m_astarDesc.m_g + 14;
			    }
			    else
			    {
                    astarDesc.m_g = fromAdjacency.m_astarDesc.m_g + 10;
			    }

			    astarDesc.m_f = astarDesc.m_h + astarDesc.m_g;
		    }
	    };
	    public AStarDesc					m_astarDesc;


	    public ADJACENCY()
        {
            reset();
        }

	    public void setAStarDesc(AStarDesc astarDesc)
	    {
		    m_astarDesc = astarDesc;
	    }

        public void reset()
        {
            m_pCallee = null;
            m_state = STATE.INIT;
            if (m_astarDesc != null)
            {
                m_astarDesc.reset();
            }
        }
    };

    public class MultiDictionary<TKey, TValue>
    {
        SortedDictionary<TKey, List<TValue>> m_dictionary = new SortedDictionary<TKey, List<TValue>>();
        public void Add(TKey key, TValue value)
        {

            if (m_dictionary.ContainsKey(key) == false)
            {
                m_dictionary[key] = new List<TValue>();
            }
            
            m_dictionary[key].Add(value);
        }

        public bool Empty()
        {
            return 0 == m_dictionary.Count();
        }

        public bool PopFromFirst(out TValue value)
        {
            if (Empty() == true)
            {
                value = default(TValue);
                return false;
            }
            value = m_dictionary.First().Value.First();
            m_dictionary.First().Value.RemoveAt(0);
            if (m_dictionary.First().Value.Count() == 0)
            {
                m_dictionary.Remove(m_dictionary.First().Key);
            }
            return true;
        }
    }
    
    public class CPathFinding
    {
        int[][] m_tileMap;
        int[] m_movable_tile_index;
        int m_occupied_tile_value;

        public enum MOVABLE_ADJANCENCY_TILE_COUNT
        {
            ADJANCENCY_COUNT_4WAY,
            ADJANCENCY_COUNT_8WAY,
        }

        public CPathFinding(int[][] tileMap, MOVABLE_ADJANCENCY_TILE_COUNT movable_adjancecy_tile_count, int occupied_tile_value)
        {            
            m_tileMap = tileMap;
            m_occupied_tile_value = occupied_tile_value;
            int width = m_tileMap[0].Length;
            switch (movable_adjancecy_tile_count)
            {
                case MOVABLE_ADJANCENCY_TILE_COUNT.ADJANCENCY_COUNT_8WAY:
                    {
                        m_movable_tile_index = new int[] {
	                          -width-1	// ↖
	                        , -width	// ↑
	                        , -width+1	// ↗
	                        , -1				// ←
	                        , 1					// →
	                        , width-1	// ↙
	                        , width		// ↓
	                        , width+1	// ↘
                        };
                    }break;
                case MOVABLE_ADJANCENCY_TILE_COUNT.ADJANCENCY_COUNT_4WAY:
                    {
                        m_movable_tile_index = new int[] {
	                          
	                        -width	// ↑
	                        , -1				// ←
	                        , 1					// →
	                        , width		// ↓
	                        
                        };
                    }break;
            }

        }

        bool isUnitMovable(byte unitSize, int map_x, int map_y)
        {
	        for (int unitY = 0; unitY < unitSize; ++unitY)
	        {
		        for (int unitX = 0; unitX < unitSize; ++unitX)
		        {
                    if (m_tileMap[map_y + unitY][map_x + unitX] == m_occupied_tile_value)
				        return false;
		        }
	        }

	        return true;
        }

        void resetAdjacency(ADJACENCY[] adjacencyContainer)
        {
            foreach (ADJACENCY item in adjacencyContainer)
            {
                item.reset();
            }
        }
        
        public bool makeAdjacencyList(out ADJACENCY[] adjacencyContainer, byte unitSize)
        {
            adjacencyContainer = new ADJACENCY[m_tileMap.Length * m_tileMap[0].Length];
            for (int i = 0; i < adjacencyContainer.Length; ++i)
            {
                adjacencyContainer[i] = new ADJACENCY();
                adjacencyContainer[i].m_position = new TILE_POSITION(0, 0);
                adjacencyContainer[i].m_adjacencyList = new List<ADJACENCY>();
                adjacencyContainer[i].m_astarDesc = new ADJACENCY.AStarDesc();
            }
            int width = m_tileMap[0].Length;
            int height = m_tileMap.Length;
	        
	        // 외곽선은 루프 돌지 않는다.
	        for (int y = 1; y < height-unitSize; ++y)
	        {
		        for (int x = 1; x < width-unitSize; ++x)
		        {
			        int adjacency_index = y*width+x;
			        ADJACENCY adjacency = adjacencyContainer[adjacency_index];
			        adjacency.m_position.m_x = x;
			        adjacency.m_position.m_y = y;

                    if (m_tileMap[y][x] == m_occupied_tile_value) continue;
			        if (isUnitMovable(unitSize, x, y) == false) continue;

                    for (byte index = 0; index < m_movable_tile_index.Length; ++index)
			        {
				        int linearIndex = adjacency_index + m_movable_tile_index[index];
                        if (m_tileMap[linearIndex / width][linearIndex % width] == m_occupied_tile_value) continue;
                        if (isUnitMovable(unitSize, linearIndex % width, linearIndex / width) == false) continue;

                        adjacency.m_adjacencyList.Add(adjacencyContainer[adjacency_index + m_movable_tile_index[index]]);
			        }
		        }
	        }
	        return true;
        }


        public bool getPathForGoalWithAStarSearch(TILE_POSITION start, TILE_POSITION goal, ADJACENCY[] adjacencyContainer, ref int[][] dynamicObjectLayer, out List<TILE_POSITION> waypointContainer)
        {
            int WIDTH = m_tileMap[0].Length;
            ADJACENCY startAdjacency = adjacencyContainer[start.getLinearIndex(WIDTH)];
            ADJACENCY goalAdjacency = adjacencyContainer[goal.getLinearIndex(WIDTH)];

            waypointContainer = new List<TILE_POSITION>();
	        MultiDictionary<int, ADJACENCY> openAdjacencyContainer = new MultiDictionary<int, ADJACENCY>();
	        openAdjacencyContainer.Add(startAdjacency.m_astarDesc.m_f, startAdjacency);

	        startAdjacency.m_pCallee = startAdjacency;

            ADJACENCY pAdjacency = null;
            while (openAdjacencyContainer.PopFromFirst(out pAdjacency) == true)
	        {           
		        
		        pAdjacency.m_state = ADJACENCY.STATE.CLOSE;
		        
		        if (pAdjacency.m_position == goalAdjacency.m_position)
		        {                    
                    waypointContainer.Insert(0, goalAdjacency.m_position);
			        while(pAdjacency.m_pCallee != startAdjacency)
			        {
                        waypointContainer.Insert(0, pAdjacency.m_pCallee.m_position);
				        pAdjacency = pAdjacency.m_pCallee;
			        }

                    resetAdjacency(adjacencyContainer);
			        return true;
		        }

		        foreach(ADJACENCY pChild in pAdjacency.m_adjacencyList)
		        {
			        if (pChild.m_state == ADJACENCY.STATE.CLOSE) continue;                    

			        ADJACENCY.AStarDesc astarDesc = new ADJACENCY.AStarDesc();
			        ADJACENCY.AStarDesc.calculate(goal, pAdjacency, pChild, astarDesc);

                    // 길찾기를 8방향으로 검색했을 때는 대각선이 나올 수 있다.
                    // OX 형태의 배열에서 O->O로 이동하려고 할 때, 부피개념이 있는 오브젝트일 경우 어색해 보일 수 있다.
                    // XO
                    // 위와 같은 경우를 체크하여, openList에 추가시키지 않도록 했다.
                    if (pAdjacency.m_position.m_x != pChild.m_position.m_x && pAdjacency.m_position.m_y != pChild.m_position.m_y)
                    {
                        int delta_x = pChild.m_position.m_x - pAdjacency.m_position.m_x;
                        int delta_y = pChild.m_position.m_y - pAdjacency.m_position.m_y;

                        if (dynamicObjectLayer[pAdjacency.m_position.m_y][pAdjacency.m_position.m_x + delta_x] > 0
                        || dynamicObjectLayer[pAdjacency.m_position.m_y + delta_y][pAdjacency.m_position.m_x] > 0)
                        {
                            continue;
                        }                        
                    } 

			        if (pChild.m_state == ADJACENCY.STATE.OPEN)
			        {
                        if (pChild.m_astarDesc.m_g < astarDesc.m_g)
				        {
					        continue;
				        }
			        }			
			
			        pChild.setAStarDesc(astarDesc);
			        pChild.m_pCallee = pAdjacency;

			        if (pChild.m_state == ADJACENCY.STATE.INIT)
			        {
                        if (dynamicObjectLayer[pChild.m_position.m_y][pChild.m_position.m_x] > 0)
                        {
                            pChild.m_state = ADJACENCY.STATE.CLOSE;
                            continue;
                        }

				        pChild.m_state = ADJACENCY.STATE.OPEN;
				        openAdjacencyContainer.Add(pChild.m_astarDesc.m_f, pChild);
			        }
					
		        }
	        }
            resetAdjacency(adjacencyContainer);
	        return false;
        }
    }
}
